package org.example.SolutionNew002;

import java.util.HashMap;
import java.util.Map;

public class LinkedList14 {
    public static void main(String[] args) {
        LinkedList14 obj=new LinkedList14();
        LRUCache cache=new LRUCache(2);
        cache.put(2,1);
        cache.put(1,1);
        cache.put(2,3);
        cache.put(4,1);
        System.out.println(cache.get(1));
        System.out.println(cache.get(2));
//        cache.put(3,2);
//        System.out.println(cache.get(2));
//        System.out.println(cache.get(3));
    }
}


class ListNodePro {
    int key;
    int val;
    ListNodePro next;
    ListNodePro prev;

    ListNodePro(){}

    ListNodePro(int x,int y) {
        key=x;
        val = y;
    }
}


class LRUCache {
    Map<Integer,ListNodePro> map=new HashMap<Integer,ListNodePro>();
    int capacity;
    int curSize;
    ListNodePro head,tail;

    public LRUCache(int capacity) {
        this.capacity=capacity;
        curSize=0;
        head=new ListNodePro();
        tail=new ListNodePro();
        head.next=tail;
        tail.prev=head;
    }

    public int get(int key) {
        ListNodePro node=map.get(key);
        if(node==null) {
            return -1;
        }
        moveToHead(node);
        return node.val;
    }

    public void put(int key, int value) {
        ListNodePro node=map.get(key);
        if(node==null) {
            ListNodePro newNode=new ListNodePro(key,value);
            map.put(key,newNode);
            addToHead(newNode);
            curSize++;
            if(curSize>capacity) {
                map.remove(tail.prev.key);
                removeNode(tail.prev);
                curSize--;
            }
        }else{
            node.val=value;
            moveToHead(node);
        }
    }

    public void moveToHead(ListNodePro node) {
        removeNode(node);
        addToHead(node);
    }

    public void addToHead(ListNodePro node) {
        node.next=head.next;
        node.prev=head;
        head.next.prev=node;
        head.next=node;
    }

    public void removeNode(ListNodePro node) {
        node.prev.next=node.next;
        node.next.prev=node.prev;
    }
}